package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
 * <p>
 * 你可以对一个单词进行如下三种操作：
 * <p>
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/edit-distance
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/1/3 12:58
 * 面试题，二刷，字符匹配题，典中典
 */
public class minDistance {
    public static void main(String[] args) {
        minDistance("horse", "ros");
    }

    // 编辑距离：op[i][j] 表示 word1 前i个字符，匹配上word2 第j个字符 所需的编辑距离
    // 首先，我们必须知道一个事实，如果 word1[i] = word2[j]，那么 op[i][j] = op[i-1][j-1]，举例：word1=ab，word2=bb，op[2][2]= op[1][1]
    // 如果 word1[i] != word2[j]，那么可以执行三种操作，删除word1[i], 插入Word2[j] 到word1[i]后，替换word1[i]为word2[j]
    // 如果是删除操作，那么 op[i][j] = op[i-1][j] + 1，删除word1[j]后，只需将word1[i-1]转化成word2[j]
    // 如果是插入操作，那么 op[i][j] = op[i][j-1] + 1，因为插入后 word[i+1] == word[j]，两者就会抵消，就变成只需将word1[i]转化成word2[j-1]
    // 如果是替换操作，那么 op[i][j] = op[i-1][j-1] + 1，word1[i]替换成word2[j]. 两者就会抵消，就变成只需将word1[i-1]转化成word2[j-1]
    // 综上，如果 word1[i] != word2[j]，op[i][j] = min(op[i-1][j], op[i][j-1], op[i-1][j-1]) + 1
    // |   | - | r | o | s |
    // | - | 0 | 1 | 2 | 3 |
    // | h | 1 | 1 | 2 | 3 |
    // | o | 2 | 2 | 1 | 2 |
    // | r | 3 | 2 | 2 | 2 |
    // | s | 4 | 3 | 3 | 2 |
    // | e | 5 | 4 | 4 | 3 |
    static public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] op = new int[m + 1][n + 1];
        // 初始化第一行
        for (int i = 0; i <= n; i++) {
            op[0][i] = i;
        }
        // 初始化第一列
        for (int i = 0; i <= m; i++) {
            op[i][0] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // word1[i] 等于 word2[j]时，动态转移方程
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    op[i][j] = op[i - 1][j - 1];
                } else { // word1[i] 不等于 word2[j]时，动态转移方程
                    op[i][j] = Math.min(Math.min(op[i - 1][j], op[i][j - 1]), op[i - 1][j - 1]) + 1;
                }
            }
        }
        return op[m][n];
    }
}
